package com.mccken.practice.top100.Top_1$20.top_8;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * @program: mccken-collect
 * @description:
 * @author: mccken
 * @create: 2024-01-01 20:42
 **/
public class FindAnagrams {

	public List<Integer> findAnagrams(String s, String p) {
		int len = s.length();
		if (len == 1) {
			return Arrays.asList(0);
		}

		// 字符-出现次数
		Map<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < p.length(); i++) {
			map.merge(p.charAt(i), 1, Integer::sum);
		}

		int valid = 0;
		Map<Character, Integer> window = new HashMap<>();
		List<Integer> res = new ArrayList<>();
		int right = 0, left = 0;
		while (right < len) {
			char right_C = s.charAt(right);
			right++;
			
			if (map.containsKey(right_C)) {
				window.merge(right_C,1,Integer::sum);
				if (window.get(right_C).equals(map.get(right_C))) {
					valid++;
				}
			}

			// 缩小window
			while (right - left == p.length()) {
				
				if (valid == map.size()) {
					res.add(left);
				}
			
				char left_C = s.charAt(left);
				left++;
				
				if (window.containsKey(left_C)) {
					if (window.get(left_C).equals(map.get(left_C))) {
						valid--;
					}
					window.merge(left_C,-1,Integer::sum);
				}
			}

		}
		return res;
	}
	
	
	// 测试用例通过了，但耗时太长。 ---> 都没有维护窗口
	public List<Integer> findAnagrams2(String s, String p) {
		int len = s.length();
		if (len == 1) {
			return Arrays.asList(0);
		}

		// 字符-出现次数
		Map<Character, Integer> map = new HashMap<>();
		for (int i = 0; i < p.length(); i++) {
			map.merge(p.charAt(i), 1, Integer::sum);
		}

		Map<Character, Integer> window = new HashMap<>();
		List<Integer> res = new ArrayList<>();
		int right = 0, left = 0;
		while (right < len) {
			right++;

			// 缩小window
			while (right - left == p.length()) {

				if (!map.containsKey(s.charAt(left))) {
					left++;
					break;
				}

				for (int i = left; i < right; i++) {
					char char_i = s.charAt(i);
					if (!map.containsKey(char_i)) {
						left++;
						window.clear();
						break;
					}
					window.merge(char_i, 1, Integer::sum);
				}
				if (window.equals(map)) {
					res.add(left);
					left++;
					window.clear();
					break;
				}
				window.clear();
				left++;
			}

		}
		return res;
	}

	public List<Integer> findAnagrams1(String s, String p) {
		int len = s.length();
		if (len == 1) {
			return Arrays.asList(0);
		}
		Set<Character> set = new HashSet<>();
		Set<Character> window = new HashSet<>();
		List<Integer> res = new ArrayList<>();
		for (int i = 0; i < p.length(); i++) {
			set.add(p.charAt(i));
		}

		int right = 0, left = 0;
		while (right < len) {
			char right_C = s.charAt(right);
			right++;

			// 缩小window
			while (right - left == p.length()) {

				if (!set.contains(s.charAt(left))) {
					left++;
					break;
				}

				for (int i = left; i < right; i++) {
					char char_i = s.charAt(i);
					if (!set.contains(char_i)) {
						left++;
						window.clear();
						break;
					}
					window.add(char_i);
				}
				if (window.equals(set)) {
					res.add(left);
					left++;
					window.clear();
					break;
				}
				window.clear();
				left++;
			}

		}

		return res;
	}

	// 要注意的是，p模式串会有重复值 比如 aab
	public static void main(String[] args) {

		FindAnagrams findAnagrams = new FindAnagrams();
		System.out.println(findAnagrams.findAnagrams("cbaebabacd", "abc"));    // [0, 6]
		System.out.println(findAnagrams.findAnagrams("abab", "ab"));              //[0, 1, 2]
		System.out.println(findAnagrams.findAnagrams("ababababab", "aab"));  // [0, 2, 4, 6]


//		HashMap<Character, Integer> map1 = new HashMap<>();
//		HashMap<Character, Integer> map2 = new HashMap<>();
//		map1.put('a', 5);
//		map1.put('c', 5);
//		
//		map2.put('c', 5);
//		map2.put('a', 5);
//
//		System.out.println(map1.equals(map2));

//		HashMap<Character, Integer> map = new HashMap<>();
//		map.put('a', 1);
//		map.merge('c', -2, Integer::sum);
//		map.merge('a', -5, Integer::sum);
//		System.out.println(map);

	}
}
